package com.njupt.Tree;

import java.util.Arrays;
import java.util.stream.Collectors;

/**
 * @Author: wujiaming
 * @CreateTime: 2024/12/3 16:26
 * @Description: 105. 从前序与中序遍历序列构造二叉树
 * @Version: 1.0
 */


public class BuildTreePreIn {

    private int currentIndex;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(inorder.length == 1 && inorder[0] == -1){
            return new TreeNode(-1);
        }
        int left = 0;
        int right = preorder.length-1;
        boolean[] flag = new boolean[preorder.length];
        return build(left,right,this.currentIndex,preorder,inorder,flag);
    }

    private TreeNode build(int left, int right, int currentIndex, int[] preorder, int[] inorder, boolean[] flag) {

        if(left>right || currentIndex<0) return null;

        int val = preorder[currentIndex];
        int mid = Arrays.stream(inorder).mapToObj(Integer::valueOf).collect(Collectors.toList()).indexOf(val);
        flag[mid] = true;
        TreeNode root = new TreeNode(val);
        int leftIndex = indexOfLeft(flag,mid);
        this.currentIndex++;
        root.left = build(leftIndex,mid-1,this.currentIndex,preorder,inorder,flag);
        int rightIndex = indexOfRight(flag,mid);
        root.right = build(mid+1,rightIndex,this.currentIndex,preorder,inorder,flag);
        return root;
    }

    private int indexOfRight(boolean[] flag, int mid) {
        int i = mid;
        for(i= mid+1;i<flag.length;i++){
            if(flag[i] == true){
                return  i-1;
            }
        }
        return i-1;
    }

    private int indexOfLeft(boolean[] flag, int mid) {
        int i = mid;
        for(i = mid-1;i>=0;i--){
            if(flag[i] == true){
                return i+1;
            }
        }
        return i+1;
    }


    public static void main(String[] args) {
        int[] preOrder = {3,9,20,15,7};
        int[] inOrder = {9,3,15,20,7};

        BuildTreePreIn test = new BuildTreePreIn();
        TreeNode root = test.buildTree(preOrder, inOrder);

        System.out.println();
    }

}
